% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx} 

\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~
Solution}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large Lab 5 -- Solution\\ \vspace{0.2em}
        {\bf Search Algorithms}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo\\
        \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Le Do Thai	}
\newcommand{\lastnamethree}{Binh   }
\newcommand{\matriculationnumberthree}{114910}


\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated

\task
Solutions to Task 1\\
a)\\
$C_1$ is optimistic, because any tile that is out of place will have to be moved at least once.\\
b)\\
$C_2$ is optimistic. because, at best, move one tile one step closer to the goal.\\
c)\\
$C_1(A)<=C_2(A)$\\

\task
Solutions to Task 2\\
\task
Solutions to Task 3\\
Yes.\\
Since we have a locally finite graph, we can be sure that every node has a finite degree. Even with disproportionally distibuted weights we will visit all nodes of height n, where n goes from 1 to infinity. If there exists a solution, we will encounter it sooner or later.\\
The only thing that could messed things up is zero node cost. It's easy to construct a model when algorithm will go deep forever. Luckily for us, costs can be only natural numbers.
\task
Solutions to Task 4\\
yes\\
using uniform cost search.
\task
Solutions to Task 5\\
yes\\
$C_p(n_k)=(c(n_k, n_{k+1})/m-k) + C_p(n_{k+1})$\\
node k+1 is the successor of node k.
\task
Solutions to Task 6\\
a)\\
define vector gamestate [0,0,0,0,0,0,....0] length= n*n\\
define operator state[i] = 1, first player set.\\
define operator state[i] = -1, second player set.\\
wining state\\
sum of one row equal 3 or -3\\
sum of one column equal 3 or -3\\
b)\\
see Ticgame.py\\
c)\\
C(n) = 1,2,0  win, loss, draw
d)\\
player 1 turn $[1, 0, 0, 0]$\\
Enter the row: 0\\
Enter the column: 1\\
player 2 turn $[1, -1, 0, 0]$\\
player 1 turn $[1, -1, 1, 0]$\\
player 1 win\\
$[[0, 0, 0, 0], [1, -1, 0, 0], [1, -1, 0, 0], [1, -1, 1, 0]]$\\

% ...













\end{document}
